W6. Логика, дискретная математика, приёмы доказательств, прямое доказательство, от противного, индукция

Автор

Zakhar Podyakov

Дата публикации

7 октября 2025 г.

Quiz | Flashcards

1. Краткое содержание

1.1 Введение в математические доказательства

Mathematical proof (математическое доказательство) — это формальный аргумент, устанавливающий истинность математического утверждения. Доказательства строятся из цепочки логических шагов: от набора предпосылок (premises) или аксиом к conclusion (выводу). Умение работать с приёмами доказательства — основа математики и computer science: так проверяют корректность алгоритмов и теорем.

1.2 Синтаксис и логические операции

Чтобы строить доказательства, используют формальный язык с фиксированным синтаксисом.

1.2.1 Символы и кванторы
  • Символы: буквы вроде \(A, B, C, ..., x, y, z\) обозначают высказывания или переменные; возможны индексы: \(A_1, B_{1,2}, x^1\).
  • Кванторы: задают «область действия» переменных.
    • Универсальный квантор (\(\forall\)): «для всех», «для каждого». Запись \(\forall x P(x)\) означает: свойство \(P(x)\) истинно для любого допустимого \(x\) в выбранной области.
    • Экзистенциальный квантор (\(\exists\)): «существует». Запись \(\exists x P(x)\) означает: найдётся хотя бы одно \(x\), для которого \(P(x)\) истинно.
1.2.2 Логические операции
  • Отрицание (\(\neg P\)): «не \(P\)»; меняет истинностное значение.
  • Конъюнкция (\(P_1 \& P_2\)): «\(P_1\) и \(P_2\)»; истинна, только если оба истинны.
  • Дизъюнкция (\(P_1 \lor P_2\)): «\(P_1\) или \(P_2\)»; истинна, если истинно хотя бы одно.
  • Импликация (\(P_1 \to P_2\)): «если \(P_1\), то \(P_2\)»; ложна только при истинном \(P_1\) и ложном \(P_2\).
  • Эквиваленция (\(P_1 \leftrightarrow P_2\)): «\(P_1\) тогда и только тогда, когда \(P_2\)»; истинна, если значения истинности совпадают.
1.3 Теоремы и условные утверждения

Theorem (теорема) — утверждение, для которого уже дано доказательство. Многие теоремы формулируются как условные утверждения.

1.3.1 Импликация: \(A \to B\)

В импликации у \(A\) и \(B\) разные роли.

  • Sufficient condition (достаточное условие): \(A\) — достаточное условие для \(B\): из истинности \(A\) следует \(B\). Пример: «делимость на 6» — достаточное условие для «делимости на 3».
  • Necessary condition (необходимое условие): \(B\) — необходимое условие для \(A\): \(A\) не может быть истинно, если ложно \(B\). Пример: «делимость на 3» — необходимое условие для «делимости на 6».
  • Contrapositive (контрапозиция): \(A \to B\) логически эквивалентно \(\neg B \to \neg A\). Доказать одно — значит доказать другое.
1.3.2 Конъюнкция в посылках: \((A_1 \& A_2 \& \dots \& A_n) \to B\)

Иногда вывод \(B\) требует одновременной истинности нескольких условий; тогда \(A_1, A_2, \dots, A_n\) вместе называют sufficient conditions (достаточными условиями) для \(B\). Пример: «прямая \(l_1\) параллельна \(l_3\)» и «прямая \(l_2\) параллельна \(l_3\)» — достаточные условия, чтобы заключить, что «\(l_1\) параллельна \(l_2\)».

1.3.3 Эквиваленция: \(A \leftrightarrow B\)

Формулировка «\(A\) тогда и только тогда, когда \(B\)» означает логическую взаимозаменяемость \(A\) и \(B\).

  • \(A\) — sufficient and necessary condition (достаточное и необходимое условие) для \(B\).
  • Чтобы доказать \(A \leftrightarrow B\), доказывают две импликации: \(A \to B\) (часть «только если») и \(B \to A\) (часть «если»).
1.4 Базовые приёмы доказательства

Argument (рассуждение, довод) — последовательность утверждений (premises, посылок), из которых логически следует итоговое утверждение (conclusion, заключение).

1.4.1 Deduction vs. induction (в смысле умозаключения, не мат. индукции)
  • Deduction (дедукция): от общих принципов к частному выводу; при истинных посылках вывод обязан быть истинным.
    • Аналогия: все лебеди белые; Дейзи — лебедь; значит, Дейзи белая.
  • Inductive reasoning (индуктивное обобщение): от частных наблюдений к общему выводу; вывод скорее всего верен, но не гарантирован.
    • Аналогия: три белых лебедя не доказывают, что все лебеди белые.
1.4.2 Direct proof (прямое доказательство)

Стандартный способ доказать импликацию \(P \to Q\).

  1. Предположить, что посылка \(P\) истинна.
  2. Использовать определения, аксиомы и уже доказанные теоремы, чтобы вывести \(Q\).
  3. Заключить, что \(Q\) истинно.

Опираются на rules of inference (правила вывода) — шаблоны логического следования.

  • Modus Ponens: из \(P\) и \(P \to Q\) следует \(Q\).
  • Hypothetical Syllogism: из \(P \to Q\) и \(Q \to R\) следует \(P \to R\).
  • Universal Instantiation: из \(\forall x P(x)\) получают \(P(c)\) для конкретного \(c\).
  • Existential Generalization: из \(P(c)\) для некоторого \(c\) получают \(\exists x P(x)\).
1.4.3 Proof by contradiction (доказательство от противного)

Непрямой приём для утверждения \(Q\) (или импликации \(P \to Q\)).

  1. Предположить противоположное тому, что нужно доказать. Для \(P \to Q\) предполагают истинность \(P\) и \(\neg Q\).
  2. Вывести логическое противоречие (например, \(X \& \neg X\)).
  3. Заключить, что исходное предположение неверно, значит, исходное утверждение истинно. Классика — иррациональность \(\sqrt{2}\).
1.4.4 Proof by mathematical induction (математическая индукция)

Доказывает, что \(P(n)\) истинно для всех целых \(n \ge n_0\): это строгая дедуктивная схема, формализующая идею «шага по натуральному ряду».

  • Simple induction (простая индукция):
    1. Basis step (база): показать \(P(n_0)\).
    2. Inductive hypothesis (индуктивное предположение): предположить \(P(k)\) для произвольного \(k \ge n_0\).
    3. Inductive step (индуктивный шаг): доказать \(P(k+1)\), используя предположение.
    4. Conclusion: по principle of mathematical induction, \(P(n)\) для всех \(n \ge n_0\).
  • Strong induction (сильная индукция):
    1. Basis step: проверить несколько начальных случаев \(P(n_0), \dots, P(n_0+m)\).
    2. Inductive hypothesis: предположить \(P(i)\) для всех \(n_0 \le i \le k\).
    3. Inductive step: доказать \(P(k+1)\) с опорой на все предыдущие.

2. Определения

  • Argument: последовательность высказываний, где начальные (premises) поддерживают финальное (conclusion).
  • Premise: утверждение, принимаемое истинным в рамках доказательства.
  • Conclusion: финальное утверждение аргумента.
  • Theorem: математическое утверждение с доказательством.
  • Sufficient condition: в \(A \to B\) формула \(A\) — достаточное условие для \(B\).
  • Necessary condition: в \(A \to B\) формула \(B\) — необходимое условие для \(A\).
  • Contrapositive для \(A \to B\): это \(\neg B \to \neg A\); эквивалентно исходной импликации.
  • Direct proof: доказательство \(P \to Q\) через цепочку шагов от \(P\) к \(Q\).
  • Proof by contradiction: предполагают \(\neg Q\) (в нужной постановке) и приходят к противоречию.
  • Mathematical induction: база + индуктивный шаг для бесконечного ряда натуральных случаев.
  • Basis step: проверка начального значения.
  • Inductive hypothesis: предположение о \(P(k)\) (или о всех меньших индексах при сильной индукции).
  • Inductive step: доказательство перехода к \(k+1\).

3. Формулы

  • Contrapositive equivalence: \(A \to B \equiv \neg B \to \neg A\)
  • Biconditional equivalence: \(A \leftrightarrow B \equiv (A \to B) \& (B \to A)\)
  • Нечётное целое: \(n = 2k + 1\)
  • Чётное целое: \(n = 2k\)
  • Сумма первых \(n\) натуральных: \[ \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \]
  • Сумма первых \(n\) квадратов: \[ \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6} \]
  • Сумма геометрической прогрессии: \[ \sum_{i=0}^{n} 2^i = 2^{n+1} - 1 \]
  • Fibonacci recurrence: \(f_n = f_{n-1} + f_{n-2}\)
  • Binet’s formula: \[ f_n = \frac{(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}} \]
  • Bernoulli’s inequality: \((1 + x)^n \ge 1 + xn\)

4. Примеры

4.1. Прямое доказательство (Лаба 5, Задание 1)

Прямым доказательством покажите, что сумма двух нечётных целых чётна.

Показать решение
  1. Предположим посылку: пусть \(x\) и \(y\) — произвольные нечётные целые.
  2. Определение нечётного целого: целое нечётно, если оно имеет вид \(2k+1\) для некоторого целого \(k\). Значит,
    • \(x = 2a + 1\),
    • \(y = 2b + 1\) для некоторых целых \(a\) и \(b\).
  3. Вычислим сумму:
    • \(x + y = (2a + 1) + (2b + 1) = 2a + 2b + 2\).
  4. Сопоставим с определением чётного: целое чётно, если оно имеет вид \(2k\). Вынесем множитель \(2\):
    • \(x + y = 2(a + b + 1)\).
  5. Заключение: так как \(a\) и \(b\) целые, то и \(a+b+1\) целое; значит, сумма есть удвоенное целое, то есть чётная.
Ответ: сумма двух нечётных целых всегда представима в виде \(2k\), то есть чётна по определению.
4.2. Прямое доказательство (Лаба 5, Задание 1.a)

Прямым доказательством покажите, что произведение двух нечётных нечётно.

Показать решение
  1. Предположим посылку: пусть \(x\) и \(y\) — произвольные нечётные целые.
  2. Определение нечётности: \(x = 2a + 1\) и \(y = 2b + 1\) для некоторых целых \(a\) и \(b\).
  3. Вычислим произведение:
    • \(x \cdot y = (2a + 1)(2b + 1) = 4ab + 2a + 2b + 1\).
  4. Сопоставим с определением нечётного: вынесем \(2\) из первых трёх слагаемых:
    • \(x \cdot y = 2(2ab + a + b) + 1\).
  5. Заключение: положим \(k = 2ab + a + b\); тогда \(k\) целое и \(xy = 2k+1\), значит произведение нечётно.
Ответ: произведение представимо в виде \(2k+1\), то есть нечётно.
4.3. Эквиваленция (Лаба 5, Задание 1.b)

Докажите: для положительного целого \(n\) число \(n\) чётно тогда и только тогда, когда \(7n+4\) чётно.

Показать решение

Чтобы доказать эквиваленцию (biconditional), нужно доказать импликацию в обе стороны.

  1. Часть 1: если \(n\) чётно, то \(7n+4\) чётно.
    • Пусть \(n\) чётно: \(n = 2k\) для некоторого целого \(k\).
    • Подставим: \(7(2k) + 4 = 14k + 4 = 2(7k + 2)\).
    • Так как \(7k+2\) целое, выражение чётно.
  2. Часть 2: если \(7n+4\) чётно, то \(n\) чётно.
    • Используем proof by contraposition (доказательство через контрапозицию). Контрапозиция к утверждению «если \(7n+4\) чётно, то \(n\) чётно» — это «если \(n\) нечётно, то \(7n+4\) нечётно».
    • Пусть \(n\) нечётно: \(n = 2k + 1\).
    • Тогда \(7(2k+1)+4 = 14k + 11 = 14k + 10 + 1 = 2(7k+5)+1\) — нечётно.
    • Контрапозиция истинна, значит исходная импликация истинна.
Ответ: обе импликации верны, поэтому эквиваленция доказана.
4.4. Эквиваленция (Лаба 5, Задание 1.c)

Докажите: \(n\) нечётно \(\Leftrightarrow\) \(5n+6\) нечётно (для положительного целого \(n\)).

Показать решение

Нужно доказать импликации в обе стороны.

  1. Часть 1: если \(n\) нечётно, то \(5n+6\) нечётно.
    • Пусть \(n = 2k+1\).
    • Тогда \(5(2k+1)+6 = 10k+11 = 10k+10+1 = 2(5k+5)+1\) — вид \(2m+1\), значит нечётно.
  2. Часть 2: если \(5n+6\) нечётно, то \(n\) нечётно.
    • По контрапозиции достаточно показать: если \(n\) чётно, то \(5n+6\) чётно.
    • Пусть \(n=2k\): \(5(2k)+6 = 10k+6 = 2(5k+3)\) — чётно.
Ответ: обе направленности верны, эквиваленция доказана.
4.5. От противного (Лаба 5, Задание 2)

Докажите от противного, что \(\sqrt{2}\) иррационально.

Показать решение
  1. Предположим противное: \(\sqrt{2}\) рационально.
  2. Определение рационального: тогда \(\sqrt{2} = a/b\), где \(a,b\) — целые, \(b \neq 0\), дробь несократима (\(a\) и \(b\) взаимно просты).
  3. Преобразуем равенство: \(\sqrt{2} = a/b \Rightarrow 2 = a^2/b^2 \Rightarrow a^2 = 2b^2\).
  4. Следствия: из \(a^2 = 2b^2\) следует, что \(a^2\) чётно, значит и \(a\) чётно; пишем \(a = 2k\).
    • Подстановка: \((2k)^2 = 2b^2 \Rightarrow 4k^2 = 2b^2 \Rightarrow b^2 = 2k^2\), значит \(b^2\) чётно и \(b\) чётно.
  5. Противоречие: \(a\) и \(b\) оба чётны — есть общий делитель \(2\), что противоречит несократимости \(a/b\).
  6. Заключение: предположение о рациональности \(\sqrt{2}\) неверно.
Ответ: \(\sqrt{2}\) иррационально.
4.6. От противного (Лаба 5, Задание 2.a)

Если \(n\) целое и \(n^3+5\) нечётно, то \(n\) чётно — от противного.

Показать решение
  1. Предположим противное: \(n^3+5\) нечётно и \(n\) нечётно.
  2. Нечётное \(n\): \(n = 2k+1\) для некоторого целого \(k\).
  3. Подстановка и упрощение:
    • \(n^3+5 = (2k+1)^3 + 5 = (8k^3+12k^2+6k+1)+5 = 8k^3+12k^2+6k+6\).
  4. Чётность: \(n^3+5 = 2(4k^3+6k^2+3k+3)\) — чётное при нечётном \(n\).
  5. Противоречие: получили чётность \(n^3+5\), хотя в посылке оно нечётно.
  6. Заключение: предположение «\(n\) нечётно» неверно, значит \(n\) чётно.
Ответ: если \(n^3+5\) нечётно, то \(n\) чётно.
4.7. От противного (Лаба 5, Задание 2.b)

Если \(3n+2\) чётно, то \(n\) чётно — от противного.

Показать решение

Нечётное \(n=2k+1\) даёт \(3n+2=6k+5=2(3k+2)+1\) — нечётно, противоречие.

Ответ: \(n\) чётно.
4.8. От противного (Лаба 5, Задание 2.c)

Для целых \(a,b\) верно \(a^2-4b\neq 2\).

Показать решение
  1. Предположим противное: \(a^2-4b=2\) для некоторых целых \(a,b\).
  2. Преобразование: \(a^2 = 4b+2 = 2(2b+1)\).
  3. Следствие: \(a^2\) чётно, значит \(a\) чётно; \(a=2k\).
  4. Подстановка: \((2k)^2 = 4b+2 \Rightarrow 4k^2 = 4b+2 \Rightarrow 2k^2 = 2b+1\).
  5. Противоречие: слева чётное, справа нечётное — равенство невозможно.
  6. Заключение: предположение неверно, значит \(a^2-4b \neq 2\) для всех целых \(a,b\).
Ответ: \(a^2-4b \neq 2\) для всех целых \(a,b\).
4.9. Математическая индукция (Лаба 5, Задание 3)

\(\displaystyle 1+2+\dots+n=\frac{n(n+1)}{2}\) для \(n\ge 1\).

Показать решение
  1. База (\(n=1\)): слева \(1\), справа \(\frac{1(1+1)}{2}=1\) — верно.
  2. Индуктивное предположение: для произвольного \(k\ge 1\) верно \(1+2+\dots+k=\frac{k(k+1)}{2}\).
  3. Индуктивный шаг (\(k+1\)): нужно \(1+\dots+k+(k+1)=\frac{(k+1)((k+1)+1)}{2}\).
    • Левая часть: \((1+\dots+k)+(k+1)=\frac{k(k+1)}{2}+(k+1)=\frac{k(k+1)+2(k+1)}{2}=\frac{(k+1)(k+2)}{2}\).
  4. Заключение: по principle of mathematical induction формула верна для всех \(n\ge 1\).
Ответ: формула доказана для всех \(n\ge 1\).
4.10. Математическая индукция (Лаба 5, Задание 3.a)

\(\displaystyle \sum_{i=0}^{n}2^i=2^{n+1}-1\).

Показать решение

Обозначим утверждение через \(P(n)\); сумма — \(\sum_{i=0}^{n}2^i\).

  1. База (\(n=0\)): слева \(2^0=1\), справа \(2^{1}-1=1\).
  2. Индуктивное предположение: для \(k\ge 0\) верно \(1+2+\dots+2^k=2^{k+1}-1\) (в смысле суммы степеней двойки до \(2^k\) включительно).
  3. Индуктивный шаг: докажем для \(k+1\):
    • хотим \(1+\dots+2^k+2^{k+1}=2^{(k+1)+1}-1\);
    • левая часть: \((2^{k+1}-1)+2^{k+1}=2\cdot 2^{k+1}-1=2^{k+2}-1\).
  4. Заключение: верно для всех \(n\ge 0\).
Ответ: равенство доказано индукцией для всех \(n\ge 0\).
4.11. Неравенство Бернулли (Лаба 5, Задание 3.b)

\((1+x)^n\ge 1+xn\) при \(n\ge 1\) и \(1+x\ge 0\).

Показать решение
  1. База (\(n=1\)): \((1+x)^1=1+x\) и \(1+1\cdot x\) — равенство.
  2. Индуктивное предположение: \((1+x)^k \ge 1+kx\) для \(k\ge 1\).
  3. Индуктивный шаг: \((1+x)^{k+1}=(1+x)^k(1+x)\). Так как \(1+x\ge 0\), умножение сохраняет знак:
    • \((1+x)^k(1+x) \ge (1+kx)(1+x)=1+x+kx+kx^2 = 1+(k+1)x+kx^2\).
    • При \(k\ge 1\) и \(x^2\ge 0\) имеем \(kx^2\ge 0\), значит \(1+(k+1)x+kx^2 \ge 1+(k+1)x\).
  4. Заключение: \((1+x)^{k+1}\ge 1+(k+1)x\); неравенство верно для всех \(n\ge 1\).
Ответ: Bernoulli’s inequality доказана для всех \(n\ge 1\) при \(1+x\ge 0\).
4.12. Математическая индукция (Лаба 5, Задание 3.c)

\(4^n>3^n+2^n\) для \(n\ge 2\).

Показать решение
  1. База (\(n=2\)): \(4^2=16 > 9+4=13\).
  2. Индуктивное предположение: \(4^k>3^k+2^k\) для \(k\ge 2\).
  3. Индуктивный шаг: \(4^{k+1}=4\cdot 4^k > 4(3^k+2^k)=4\cdot 3^k+4\cdot 2^k = 3^{k+1}+3^k+2^{k+1}+2^{k+1}\).
    • При \(k\ge 2\) величины \(3^k\) и \(2^{k+1}\) положительны, поэтому \(3^{k+1}+3^k+2^{k+1}+2^{k+1} > 3^{k+1}+2^{k+1}\).
  4. Заключение: \(4^{k+1}>3^{k+1}+2^{k+1}\); неравенство верно для всех \(n\ge 2\).
Ответ: неравенство доказано для всех \(n\ge 2\).
4.13. Математическая индукция (Лаба 5, Задание 3.d)

\(4^n-1\) делится на \(3\) для всех \(n\ge 1\).

Показать решение
  1. База (\(n=1\)): \(4^1-1=3\).
  2. Индуктивное предположение: \(4^k-1=3m\), то есть \(4^k=3m+1\).
  3. Индуктивный шаг: \(4^{k+1}-1=4\cdot 4^k-1=4(3m+1)-1=12m+3=3(4m+1)\).
  4. Заключение: делимость на \(3\) для всех \(n\ge 1\).
Ответ: по индукции \(3\mid (4^n-1)\) для всех \(n\ge 1\).
4.14. Математическая индукция (Лаба 5, Задание 3.e)

\(5^n-4n+15\) делится на \(16\) при \(n\ge 0\).

Показать решение
  1. База (\(n=0\)): \(5^0-0+15=16\).
  2. Индуктивное предположение: \(5^k-4k+15=16m\), откуда \(5^k=16m+4k-15\).
  3. Индуктивный шаг: \(5^{k+1}-4(k+1)+15=5\cdot 5^k-4k+11=5(16m+4k-15)-4k+11=80m+16k-64=16(5m+k-4)\).
  4. Заключение: делимость на \(16\) для всех \(n\ge 0\).
Ответ: по индукции \(16\mid (5^n-4n+15)\) для всех \(n\ge 0\).
4.15. Вывод заключения (Туториал 5, Задание 1)

Каково логическое заключение из утверждений ниже?

  • Если сегодня идёт дождь, нужно взять зонт.
  • Сегодня идёт дождь.
Показать решение
  1. Посылки: пусть \(P\) — «сегодня дождь», \(Q\) — «нужен зонт». Даны \(P\to Q\) и \(P\).
  2. Правило вывода: это схема Modus Ponens: из истинности импликации и её посылки следует заключение.
  3. Заключение: \(Q\) истинно.
Ответ: зонт нужен (заключение \(Q\)).
4.16. Вывод заключения (Туториал 5, Задание 2)

Каково логическое заключение из утверждений ниже?

  • Если у Джорджа не восемь ног, то он не паук.
  • Джордж — паук.
Показать решение
  1. Посылки: пусть \(P\) — «у Джорджа не 8 ног», \(Q\) — «он не паук». Первая посылка: \(P\to Q\). Вторая: Джордж — паук, то есть \(\neg Q\).
  2. Правило вывода: Modus Tollens — из \(P\to Q\) и \(\neg Q\) следует \(\neg P\).
  3. Заключение: \(\neg P\), то есть «у Джорджа восемь ног».
Ответ: у Джорджа восемь ног.
4.17. Вывод заключения (Туториал 5, Задание 3)

Что логически следует для студента Боба из утверждений ниже?

  • Каждый из 93 студентов этого курса имеет персональный компьютер: \((\forall x\in Cl)\,PC(x)\).
  • Каждый, кто имеет персональный компьютер, умеет пользоваться текстовым процессором: \((\forall x)\,(PC(x)\to WP(x))\).
Показать решение
  1. Посылки: (1) для любого студента \(x\) курса \(Cl\) верно \(PC(x)\); (2) для любого человека \(x\) из \(PC(x)\) следует \(WP(x)\).
  2. Universal instantiation: так как Боб — студент курса, из (1) получаем \(PC(\text{Боб})\).
  3. Modus ponens: подставляя в (2), из \(PC(\text{Боб})\) следует \(WP(\text{Боб})\).
Ответ: Боб умеет пользоваться текстовым процессором.
4.18. Прямое доказательство (Туториал 5, Задание 4)

Прямым доказательством покажите, что сумма двух нечётных целых чётна.

Показать решение
  1. Посылка: пусть \(x,y\) — произвольные нечётные целые.
  2. Определение: \(x=2a+1\), \(y=2b+1\) для целых \(a,b\).
  3. Сумма: \(x+y=(2a+1)+(2b+1)=2a+2b+2\).
  4. Чётность: \(x+y=2(a+b+1)\).
  5. Заключение: \(a+b+1\) целое, значит сумма — удвоенное целое.
Ответ: сумма имеет вид \(2k\), то есть чётна.
4.19. Доказательство через контрапозицию (Туториал 5, Задание 5)

Докажите: если \(n\) целое и \(3n+2\) нечётно, то \(n\) нечётно.

Показать решение
  1. Контрапозиция: «если \(P\), то \(Q\)» эквивалентно «если \(\neg Q\), то \(\neg P\)». Здесь \(P\): «\(3n+2\) нечётно», \(Q\): «\(n\) нечётно». Контрапозиция: если \(n\) чётно, то \(3n+2\) чётно.
  2. Предположим: \(n\) чётно.
  3. Запись: \(n=2k\).
  4. Подстановка: \(3n+2=3(2k)+2=6k+2=2(3k+1)\).
  5. Заключение: \(3n+2\) чётно — контрапозиция доказана, значит исходная импликация верна.
Ответ: исходное утверждение истинно.
4.20. От противного (Туториал 5, Задание 6)

Докажите от противного, что \(\sqrt{2}\) иррационально.

Показать решение
  1. Предположим \(\sqrt{2}=a/b\) в несократимой дроби.
  2. Тогда \(a^2=2b^2\), откуда \(a\) чётно: \(a=2k\).
  3. Подстановка даёт \(b^2=2k^2\), значит \(b\) чётно.
  4. Общий делитель \(2\) противоречит несократимости.
  5. Значит предположение о рациональности \(\sqrt{2}\) ложно.
Ответ: \(\sqrt{2}\) иррационально.
4.21. Математическая индукция (Туториал 5, Задание 7)

Докажите по индукции: \(\displaystyle\sum_{i=1}^n i=\frac{n(n+1)}2\) для любого \(n\ge 1\).

Показать решение
  1. База (\(n=1\)): левая часть (LHS) равна \(1\); правая (RHS) \(\frac{1\cdot 2}{2}=1\).
  2. Индукционное предположение: \(\sum_{i=1}^k i=\frac{k(k+1)}{2}\).
  3. Шаг: \(\sum_{i=1}^{k+1}i=\frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}\).
  4. Заключение: по принципу математической индукции формула верна для всех \(n\ge 1\).
Ответ: формула доказана.
4.22. Математическая индукция (Туториал 5, Задание 8)

Докажите по индукции: \(\displaystyle\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}6\) для \(n\ge 1\).

Показать решение
  1. База (\(n=1\)): \(1^2=1\) и \(\frac{1\cdot 2\cdot 3}{6}=1\).
  2. Предположение: \(\sum_{i=1}^k i^2=\frac{k(k+1)(2k+1)}{6}\).
  3. Шаг: прибавляем \((k+1)^2\) и приводим к общему виду \[(k+1)\left(\frac{k(2k+1)}{6}+(k+1)\right)=(k+1)\frac{(k+2)(2k+3)}{6}=\frac{(k+1)(k+2)(2(k+1)+1)}{6}.\]
  4. Заключение: формула верна для всех \(n\ge 1\).
Ответ: тождество доказано индукцией.
4.23. Формула Бине (Туториал 5, Задание 9)

\(f_n=\dfrac{\big(\frac{1+\sqrt5}2\big)^n-\big(\frac{1-\sqrt5}2\big)^n}{\sqrt5}\).

Показать решение

Это Binet’s formula — явная формула для \(f_n\) при \(f_0=0,f_1=1\), \(f_n=f_{n-1}+f_{n-2}\); связь с golden ratio \(\varphi=\frac{1+\sqrt5}2\).

Ответ: формула Бине для \(n\)-го числа Фибоначчи.
4.24. Математическая индукция (Туториал 5, Задание 10)

Докажите по индукции: \(f_1+f_3+\dots+f_{2n-1}=f_{2n}\) для любого \(n\ge 1\).

Показать решение
  1. База (\(n=1\)): слева \(f_1=1\), справа \(f_2=1\).
  2. Предположение: \(f_1+f_3+\dots+f_{2k-1}=f_{2k}\).
  3. Шаг: добавляем \(f_{2k+1}\): левая часть \(f_{2k}+f_{2k+1}=f_{2k+2}\) по рекуррентному соотношению Фибоначчи; это и есть правая часть для \(n=k+1\).
  4. Заключение: тождество верно для всех \(n\ge 1\).
Ответ: сумма \(f_1,\dots,f_{2n-1}\) равна \(f_{2n}\).